/*
https://leetcode.cn/problems/scramble-string/description/
87. 扰乱字符串
方钊堉 2024.10.19
区间dp
*/
class Solution {
private:
    bool dp[30][30][30] = {false}; // 动态规划数组，dp[start1][end1][start2] 表示 s2[start2 : end1] 是否能由 s1[start1 : start1 + (end1 - start2)] 打乱得到

public:
    bool isScramble(string s1, string s2) {
        int size = s1.size();

        // 初始化单字符情况
        for (int i = 0; i < size; i++) {
            for (int start2 = 0; start2 < size; start2++) {
                dp[i][i][start2] = (s2[i] == s1[start2]);
            }
        }

        // 枚举所有可能的子串长度
        for (int length = 2; length <= size; length++) {
            // 枚举所有可能的起始位置
            for (int start1 = 0; start1 < size; start1++) {
                int end1 = start1 + length - 1;
                if (end1 >= size) break;

                // 枚举所有可能的起始位置
                for (int start2 = 0; start2 < size; start2++) {
                    int end2 = start2 + length - 1;
                    if (end2 >= size) break;

                    // 枚举分割点，不交换顺序
                    for (int split = start1; split < end1 && !dp[start1][end1][start2]; split++) {
                        dp[start1][end1][start2] = dp[start1][split][start2] && dp[split + 1][end1][split + 1 + start2 - start1];
                    }

                    // 枚举分割点，交换顺序
                    for (int split = start1; split < end1 && !dp[start1][end1][start2]; split++) {
                        dp[start1][end1][start2] = dp[start1][split][end2 - (split - start1)] && dp[split + 1][end1][start2];
                    }
                }
            }
        }

        return dp[0][size - 1][0]; // 返回整个字符串的打乱结果
    }
};